class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<int> dp(s.size());
        unordered_set<string> wd_set;
        for(auto wd : wordDict)
            wd_set.insert(wd);

        for(int i = 0; i < s.size(); i++)
        {
            for(int j = 0; j <= i; j++)
            {
                string str = s.substr(j, i-j+1);
                if(wd_set.count(str) > 0)
                {
                    if(j>0)
                        dp[i] = max(dp[j-1],dp[i]);
                    else
                        dp[i] = 1;
                }
            }
        }

        return dp[s.size()-1];
    }
};